package com.jack.leetcode.eachProblem07;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhang_j on 2020/7/14
 */
public class 三角形最小路径和 {

    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) {
        List<List<Integer>> tri = new ArrayList<>();
        for(int i = 0;i < 4;i++){
            List<Integer> a = new ArrayList<>();
            for(int j = 1;j < i+2;j++){
                a.add(j);
            }
            tri.add(a);
        }
        System.out.println(minimumTotal(tri));
    }

    public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n+1];
        for(int i = n-1;i >= 0;i--){
            for(int j = 0;j <= i;j++){
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

    private static int getMin(List<List<Integer>> triangle, int i, int j){
        if(i == triangle.size()){
            return 0;
        }
        return Math.min(getMin(triangle, i+1, j),
                triangle.get(i).get(j) + getMin(triangle, i+1, j+1));
    }

//    public static void main(String[] args) {
//        int numApproxElements = 1000000;
//        double fpp = 0.0001;
//        int result = (int) (-numApproxElements * Math.log(fpp) / (Math.log(2) * Math.log(2)));
//        System.out.println(result);
//        int max = Math.max(1, (int) Math.round((double) result / numApproxElements * Math.log(2)));
//        System.out.println(max);
//    }
}
